package zhengqc.heap;

import zhengqc.list.ArrayList;

public class MinHeap<E extends Comparable<E>> extends AbstractHeap<E> {
    public MinHeap(int capacity) {
        this.data = new ArrayList<>(capacity);
    }
    public MinHeap() {
        this.data = new ArrayList<>();
    }
    public MinHeap(E[] array) {
        this.data = new ArrayList<>(array);
        this.heapify();
    }
    @Override
    protected void siftUp(int index) {
        while ( (index > 0) &&
                (data.get(parent(index)).compareTo(data.get(index)) > 0) ) {
            data.swap(index, parent(index));
            index = parent(index);
        }
    }
    @Override
    protected void siftDown(int index) {
        // 当没有左孩子（此时也没有右孩子）时, 结束 sift down
        while (leftChild(index) < data.getSize()) {
            int j = leftChild(index);
            // 当有右孩子且右孩子的值小于左孩子的值, 则指针 j 指向 右孩子
            if ( (j + 1 < data.getSize()) &&
                    (data.get(j+1).compareTo(data.get(j)) < 0) ) {
                ++ j; // data[j] 是 data[leftChild] 和 data[rightChild] 中的最小值
            }
            // 如果 data[index] 的值不大于 data[j]（即同时不大于左右孩子节点的值）, 则停止 sift down
            if ( data.get(index).compareTo(data.get(j)) <= 0 ) {
                break;
            }
            data.swap(index, j);
            index = j;
        }
    }
    @Override
    public String toString() {
        return "MinHeap: " + super.toString();
    }
}
